package Review;



public class Test34 {

	public static void main(String[] args) {
//		System.out.println(Ugly.getNumberOfnUgly(1500));
		System.out.println(ugly(1500));

	}
	public static int ugly(int n){
		if(n<1){
			System.out.println("�������ݲ��Ϸ�");
			return -1;
		}
		int count = 0;
		int num = 0;
		while(count<n){
			num++;
			if(isUgly(num)){
				count++;
			}
		}
		return num;
	}
	public static boolean isUgly(int num){
		while(num %2 ==0){
			num /=2;
		}
		while(num %3 ==0){
			num /= 3;
		}
		while(num %5==0){
			num /= 5;
		}
		if(num == 1){
			return true;
		}
		else{
			return false;
		}
	}

}
class Ugly{
	public static int getNumberOfnUgly(int n){
		int []a = new int[n];
		a[0] = 1;
		int count = 1;
		int index2 = 0;
		int index3 = 0;
		int index5 = 0;
		while(count < n){
			int minValue = min(a[index2] * 2, a[index3] * 3,a[index5] * 5);
			a[count] = minValue;
			while(index2 < count && a[index2]*2 <= a[count]) index2 ++;
			while(index3 < count && a[index3]*3 <= a[count]) index3 ++;
			while(index5 < count && a[index5]*5 <= a[count]) index5 ++;
			count ++;
		}
		return a[n - 1];
	}
	public static int min(int a,int b , int c){
		return (a < b)?((a < c)?a:c ):((b < c) ? b : c);
	}
}
